{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the K-or of an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKOr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出数组中的 K-or 值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p><code>nums</code> 中的 <strong>K-or</strong> 是一个满足以下条件的非负整数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>只有在 <code>nums</code> 中，至少存在 <code>k</code> 个元素的第 <code>i</code> 位值为 1 ，那么 K-or 中的第 <code>i</code> 位的值才是 1 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <code>nums</code> 的 <strong>K-or</strong> 值。</p>\n",
    "\n",
    "<p><strong>注意</strong> ：对于整数 <code>x</code> ，如果&nbsp;<code>(2<sup>i</sup> AND x) == 2<sup>i</sup></code> ，则 <code>x</code> 中的第 <code>i</code> 位值为 1 ，其中 <code>AND</code> 为按位与运算符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [7,12,9,8,9,15], k = 4\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。\n",
    "nums[0] 和 nums[5] 的第 1 位的值为 1 。\n",
    "nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。\n",
    "nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。\n",
    "只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此，答案为 2^0 + 2^3 = 9 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,12,1,11,4,5], k = 6\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>因为 k == 6 == nums.length ，所以数组的 6-or 等于其中所有元素按位与运算的结果。因此，答案为 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,8,5,9,11,6,8], k = 1\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>因为 k == 1 ，数组的 1-or 等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt; 2<sup>31</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-k-or-of-an-array](https://leetcode.cn/problems/find-the-k-or-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-k-or-of-an-array](https://leetcode.cn/problems/find-the-k-or-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,12,9,8,9,15]\\n4', '[2,12,1,11,4,5]\\n6', '[10,8,5,9,11,6,8]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKOr(self, nums: List[int], k: int) -> int:\n",
    "        # If k is 1, return the bitwise OR of all numbers\n",
    "        if k == 1:\n",
    "            result = 0\n",
    "            for num in nums:\n",
    "                result |= num\n",
    "            return result\n",
    "\n",
    "        # If k equals the length of nums, return the bitwise AND of all numbers\n",
    "        if k == len(nums):\n",
    "            result = nums[0]\n",
    "            for num in nums[1:]:\n",
    "                result &= num\n",
    "            return result\n",
    "\n",
    "        # Otherwise, count the number of numbers with each bit set\n",
    "        bit_counts = [0] * 32  # Assuming 32-bit integers for simplicity\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                if (num >> i) & 1:\n",
    "                    bit_counts[i] += 1\n",
    "\n",
    "        # Set bits in the result where the count is at least k\n",
    "        result = 0\n",
    "        for i in range(32):\n",
    "            if bit_counts[i] >= k:\n",
    "                result |= (1 << i)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKOr(self, nums: List[int], k: int) -> int:\n",
    "        kor = 0\n",
    "        maxBit = 1 << 30\n",
    "        bit = 1\n",
    "        while bit <= maxBit:\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                if num & bit != 0:\n",
    "                    count += 1\n",
    "                    if count == k:\n",
    "                        kor |= bit\n",
    "                        break\n",
    "            bit <<= 1\n",
    "        return kor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKOr(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for t in range(31):\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if 1 << t & num == 1 << t:\n",
    "                    cnt += 1\n",
    "            if cnt >= k:\n",
    "                ans += 1 << t\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKOr(self, nums: List[int], k: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for x in nums:\n",
    "            while x:\n",
    "                lb = x & (-x)\n",
    "                d[lb] += 1\n",
    "                x -= lb\n",
    "        return sum(key for key, v in d.items() if v >= k)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
